The present invention relates to systems and methods for decoding data, and more particularly, to systems and methods for decoding multi-stage information additive codes, herein referred to collectively as “Raptor Codes.”
Chain reaction codes have been described previously in the assignee's patents, such as U.S. Pat. No. 6,307,487 entitled “Information Additive Code Generator and Decoder for Communication Systems” (hereinafter “Luby I”), and U.S. Pat. No. 7,068,729 entitled “Multi-Stage Code Generator and Decoder for Communication Systems” (hereinafter “Raptor”). As described therein, chain reaction coding is a form of forward error-correction that enables data reconstruction from a received data set of a sufficient size, regardless of which portions of the transmitted data set are received. Communication systems employing chain reaction codes are able to communicate information much more efficiently compared to traditional FEC codes transmitted via data carousel or acknowledgement-based protocols, as described in Luby I or Raptor.
Transmission of data between a sender and a recipient over a communications channel has been the subject of much literature. Preferably, but not exclusively, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity (which covers most of all physically realizable systems), one concern is how to deal with data lost or garbled in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always tell when corrupted data is data received in error. Many error-correcting codes have been developed to correct for erasures and/or for errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected, a simple parity code might be best.
Data transmission between multiple senders and/or multiple receivers over a communications channel has also been the subject of much literature. Typically, data transmission from multiple senders requires coordination among the multiple senders to allow the senders to minimize duplication of efforts. In a typical multiple sender system sending data to a receiver, if the senders do not coordinate which data they will transmit and when, but instead just send segments of the file, it is likely that a receiver will receive many useless duplicate segments. Similarly, where different receivers join a transmission from a sender at different points in time, a concern is how to ensure that all data the receivers receive from the sender is useful. For example, suppose the sender is wishes to transmit a file, and is continuously transmitting data about the same file. If the sender just sends segments of the original file and some segments are lost, it is likely that a receiver will receive many useless duplicate segments before receiving one copy of each segment in the file. Similarly, if a segment is received in error multiple times, then the amount of information conveyed to the receiver is much less than the cumulative information of the received garbled data. Often this leads to undesirable inefficiencies of the transmission system.
Often data to be transmitted over a communications channel is partitioned into equal size input symbols. The “size” of an input symbol can be measured in bits, whether or not the input symbol is actually broken into a bit stream, where an input symbol has a size of M bits when the input symbol is selected from an alphabet of 2M symbols.
A coding system may produce output symbols from the input symbols. Output symbols are elements from an output symbol alphabet. The output symbol alphabet may or may not have the same characteristics as the alphabet for the input symbols. Once the output symbols are created, they are transmitted to the receivers.
The task of transmission may include post-processing of the output symbols so as to produce symbols suitable for the particular type of transmission. For example, where transmission constitutes sending the data from a wireless provider to a wireless receiver, several output symbols may be lumped together to form a frame, and each frame may be converted into a wave signal in which the amplitude or the phase is related to the frame. The operation of converting a frame into a wave is often called modulation, and the modulation is further referred to as phase or amplitude modulation depending on whether the information of the wave signal is stored in its phase or in its amplitude. Nowadays this type of modulated transmission is used in many applications, such as satellite transmission, cable modems, Digital Subscriber Lines (DSL), and many others.
A transmission is called reliable if it allows the intended recipient to recover an exact copy of the original data even in the face of errors and/or erasures during the transmission. Recovery of erased information has been the subject of much literature and very efficient coding methods have been devised in this case. Chain reaction codes, as described in Luby I or Raptor, are among the most efficient coding methods known to date for recovery of erasures in a wide variety of settings.
One solution that has been proposed to increase reliability of transmission is to use Forward Error-Correction (FEC) codes, such as Reed-Solomon codes, Tornado codes, or Low Density Parity Check (LDPC) codes. With such codes, one sends output symbols generated from the content instead of just sending the input symbols that constitute the content. Traditional error correcting codes, such as Reed-Solomon or other LDPC codes, generate a fixed number of output symbols for a fixed length content. For example, for K input symbols, N output symbols might be generated. These N output symbols may comprise the K original input symbols and N-K redundant symbols. If storage permits, then the sender can compute the set of output symbols for each piece of data only once and transmit the output symbols using a carousel protocol.
One problem with some FEC codes is that they require excessive computer power or memory to implement. Another problem is that the number of output symbols must be determined in advance of the coding process. This can lead to inefficiencies if the error rate of the symbols is overestimated, and can lead to failure if the error rate is underestimated. Moreover, traditional FEC schemes often require a mechanism to estimate the reliability of the communications channel on which they operate. For example, in wireless transmission the sender and the receiver are in need of probing the communications channel so as to obtain an estimate of the noise and hence of the reliability of the channel. In such a case, this probing has to be repeated quite often, since the actual noise is a moving target due to rapid and transient changes in the quality of the communications channel.
For traditional FEC codes, the number of valid output symbols that can be generated is of the same order of magnitude as the number of input symbols the content is partitioned into and is often a fixed ratio called the “code rate.” Typically, but not exclusively, most or all of these output symbols are generated in a preprocessing step before the sending step. These output symbols have the property that all the input symbols can be regenerated from any subset of the output symbols equal in length to the original content or slightly longer in length than the original content.
Chain reaction decoding described in Luby I and Raptor is a different form of forward error-correction that addresses the above issues in cases where a transmission error constitutes an erasure. For chain reaction codes, the pool of possible output symbols that can be generated is orders of magnitude larger than the number of the input symbols, and a random output symbol from the pool of possibilities can be generated very quickly. For chain reaction codes, the output symbols can be generated on the fly on an as needed basis concurrent with the sending step. Chain reaction codes have the property that all input symbols of the content can be regenerated from any subset of a set of randomly generated output symbols slightly longer in length than the original content.
Other descriptions of various chain reaction coding systems can be found in documents such as U.S. Pat. No. 6,486,803, entitled “On Demand Encoding with a Window” and U.S. Pat. No. 6,411,223 entitled “Generating High Weight Output symbols using a Basis,” assigned to the assignee of the present application.
Some embodiments of a chain reaction coding system comprise an encoder and a decoder. Data may be presented to the encoder in the form of a block, or a stream, and the encoder may generate output symbols from the block or the stream on the fly. In some embodiments, for example those described in Raptor, data may be pre-encoded off-line, or concurrently with the process of transmission, using a static encoder, and the output symbols may be generated from the static input symbols, defined as the plurality of the original data symbols, and the output symbols of the static encoder. In general, the block or stream of symbols from which the dynamic output symbols are generated is referred to herein as “source symbols.” Thus, in the case of the codes described in Raptor, the source symbols are the static input symbols, while for codes described in Luby I the source symbols are the input symbols. The term “input symbols” herein refers to the original symbols presented to the encoder for encoding. Thus, for chain reaction codes described in Luby I, the source symbols are identical with input symbols. Sometimes, to distinguish between a Raptor Code, as for example one of the codes described in Raptor, and the codes described in Luby I, we will refer to the output symbols generated by a coding system employing a Raptor Code as the “dynamic output symbols.”
In certain applications, it may be preferable to transmit the source symbols first, and then continue transmission by sending output symbols. Such a coding system is called a systematic coding system and systematic coding systems for codes such as those described in Luby I and Raptor are disclosed in U.S. Pat. No. 6,909,383 entitled “Systematic Encoding and Decoding of Chain Reaction Codes” (hereinafter “Systematic Raptor”).
Various methods for generating source symbols from the input symbols are described in Raptor. Generally, but not exclusively, the source symbols are preferably generated efficiently on a data processing device, and, at the same time, a good erasure correcting capability is required of the multi-stage code. One of the teachings in Raptor is to use a combination of codes to produce the source symbols. In one particular embodiment, this combination comprises using a Hamming encoder to produce a first plurality of source symbols and then using an LDPC code to produce a second set of source symbols from which the dynamic output symbols are calculated.
Other methods and processes for both the generation of source symbols and dynamic output symbols have been discussed in U.S. Pat. No. 6,856,263 entitled “Systems and Processes for Decoding a Chain Reaction Code Through Inactivation” (hereinafter “Inactivation Decoding”). One advantage of a decoder according to Inactivation Decoding over a multi-stage chain reaction decoder described in Raptor is that the Inactivation Decoding decoder has typically a lower probability of error.
The encoding for a Raptor encoder in some embodiments can be partitioned into two stages. The first stage computes redundant symbols from the original input symbols, and the second stage generates output symbols from the combination of the original input symbols and redundant symbols. In some embodiments of a Raptor encoder, the first stage can be further partitioned into two or more steps, where some of these steps compute redundant symbols based on Low Density Parity Check (LDPC) codes or other codes, and where other steps compute redundant symbols based on other codes. To lower the probability of error of the decoder, both multi-stage chain reaction decoding and some embodiments of decoding described in Inactivation Decoding make use of an extended Hamming code in these other steps, and thus an extended Hamming code is used in these embodiments in one of the primary stages of static encoding.
As is well known to those skilled in the art, a Hamming code generates, for a given number k of input symbols, a number k+r+1 of source symbols, wherein the first k source symbols coincide with the input symbols, and the additional r+1 source symbols (referred to as the “Hamming redundant symbols” hereinafter) are calculated. The number r is the smallest integer with the property illustrated in Equation 1.2r−1−r≦k<2r−r−1  (Equ. 1)
The Hamming redundant symbols are calculated in a specific way from the input symbols. Using the naïve method for the computation of these symbols, each Hamming redundant symbol requires on average around k/2 XORs of input symbols. In total, the calculation of the r+1 Hamming redundant symbols requires around (k/2)·r XORs of input symbols. Since r is of the order log(k), this amounts to roughly k·log(k)/2 XORs of input symbols for the calculation of the Hamming redundant symbols. Taking into account that the additional redundant symbols calculated via, for example LDPC encoding, require much less computational time, the calculation of the Hamming redundant symbols using the naïve approach would constitute a computational bottleneck for the design of some embodiments of reliable multi-stage encoders.
What is therefore needed is an apparatus or process for calculating the Hamming redundant symbols that is much more efficient than the naïve one, and can be implemented easily on various computing devices.